---
id: 5900f4021000cf542c50ff13
title: 'Завдання 149: пошук підпослідовностей з максимальною сумою'
challengeType: 1
forumTopicId: 301778
dashedName: problem-149-searching-for-a-maximum-sum-subsequence
---

# --description--

Завдяки таблиці нижче легко переконатися, що максимальною можливою сумою суміжних чисел у будь-якому напрямку (горизонтальному, вертикальному, діагональному) є $16 (= 8 + 7 + 1)$.

$$\begin{array}{|r|r|r|r|} \hline −2 &  5 &  3 & 2 \\\\ \hline 9 & −6 &  5 & 1 \\\\ \hline 3 &  2 &  7 & 3 \\\\ \hline −1 &  8 & −4 & 8 \\\\ \hline \end{array}$$

Тепер повторимо пошук, але в набагато більшому масштабі:

Для початку згенеруйте чотири мільйони псевдовипадкових чисел, використовуючи конкретну форму того, що відомо як «генератор Фібоначчі»:

За умови $1 ≤ k ≤ 55$, $s_k = (100003 − 200003k + 300007{k}^3) \\ (modulo\\ 1000000) − 500000$.

За умови $56 ≤ k ≤ 4000000$, $s_k = (s_{k − 24} + s_{k − 55} + 1000000) \\ (modulo\\ 1000000) − 500000$.

Таким чином, $s_{10} = −393027$ та $s_{100} = 86613$.

Потім члени $s$ розташовуються в таблиці 2000×2000, використовуючи перші 2000 чисел для заповнення першого рядка (послідовно), наступні 2000 чисел — для заповнення другого рядка і так далі.

Знайдіть найбільшу суму будь-якої кількості суміжних записів в будь-якому напрямку (горизонтальному, вертикальному чи діагональному).

# --hints--

`maximumSubSequence()` має повернути `52852124`.

```js
assert.strictEqual(maximumSubSequence(), 52852124);
```

# --seed--

## --seed-contents--

```js
function maximumSubSequence() {

  return true;
}

maximumSubSequence();
```

# --solutions--

```js
// solution required
```
